

#define MAX(A,B) ((A)>(B)? (A):(B))

// 定义状态：dp[i]表示以nums[i]结尾序列的长度
// 状态转换：只要nums[i]严格大于在它位置之前的某个数，那么nums[i]就可以 "接在这个数后面" 形成一个更长的上升子序列
int lengthOfLIS(int* nums, int numsSize){
    if (numsSize < 2) return numsSize;
    int res = 0, *dp = malloc(sizeof(int)*numsSize);

    for (int i = 0; i < numsSize; i++)
        dp[i] = 1;

    for (int i = 0; i < numsSize; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i])  
                dp[i] = MAX(dp[i], dp[j]+1);
        }
    }

    for (int i = 0; i < numsSize; i++) {
        if (dp[i] > res) res = dp[i];
    }
    return res;
}
// https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/dong-tai-gui-hua-er-fen-cha-zhao-tan-xin-suan-fa-p/